module(..., package.seeall) 

gr = require "graphs"
st = require "stacks" 
r = require "random"

function timer() 
   local time = 0 
   return
   function () 
      time = time+1 
      return time 
   end
end 


function build_random_graph (nodes, density) 
   local g = gr.make_graph(nodes) 
   local approx_card = nodes*density

   local function choose_some_neighbors (i) 
      g[i] = {} 	 
      for _,j in ipairs(r.random_subset(nodes,approx_card)) do 
	 if j ~= i then 
	    table.insert(g[i], {dst = j})
	 end 	    
      end 
   end
   for i = 1,g.length do 
      choose_some_neighbors (i)
   end
   return g 
end 

function build_random_undirected_graph(nodes,density) 
   local g = gr.make_graph(nodes) 
   local approx_card = nodes*density

   local function choose_some_neighbors (i) 
      --      g[i] = {} 	 
      for _,j in ipairs(r.random_subset(nodes,approx_card)) do 
	 if j ~= i then 
	    table.insert(g[i], {dst = j})
	    table.insert(g[j], {dst = i})
	 end 	    
      end 
   end
   for i = 1,g.length do 
      choose_some_neighbors (i)
   end
   return g 
end 

function reverse(a) 
   result = {} 
   for i = #a,1,-1 do 
      result[#a-i+1] = a[i]
   end 
   return result 
end 


function extract_acyclic_subgraph(g) 
   local result = { length = g.length }
   local dfs_results = {} 
   local time = timer() 
   local s = st.new() 

   -- the fn push_new_neighbors goes through the 
   -- neighbors of i and pushes any new neighbors j, 
   -- as indicated by not yet having any dfs_results[j].  
   -- mark the current time and the predecessor i.  

   local function push_new_neighbors (i) 
      result[i] = {} 
      for _,e in ipairs(g[i]) do 
	 local j = e.dst
	 if not(dfs_results[j])
	 then 
	    dfs_results[j] = { disc = time(), pi = i } 
	    table.insert(result[i], {dst = j}) 
	    st.push(s,j)
	 else if dfs_results[j].fin or dfs_results[i].disc<dfs_results[j].disc 
	    then 	    
	       table.insert(result[i], {dst = j}) 
	    end
	 end 
      end
   end	 

   -- we walk through the nodes.  
   -- if we havent seen a node before, we push it
   -- and then as long as the stack is non-empty we
   -- push new neighbors 
   -- or else pop off nodes, marking them as finished 

   for i = 1,g.length do 
      if not(dfs_results[i])
      then 
	 dfs_results[i] = { disc = time() , pi = false } 
	 st.push(s,i)
	 while (not(st.empty(s))) do 
	    local i = st.top(s)
	    local t = dfs_results[i]
	    if t.neighbors_done 
	    then 
	       t.fin = time() 
	       st.pop(s) 
	    else
	       push_new_neighbors(i) 
	       t.neighbors_done = true 
	    end
	 end
      end
   end
   return result 
end

function build_random_dag(nodes, density)
   return extract_acyclic_subgraph(build_random_graph (nodes, density))
end

